import java.util.HashMap;
import java.util.Map;

public class Solution1145 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    Map<TreeNode,Integer> map=new HashMap<>();

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int total=cal(root);
        TreeNode target=find(x,root);
        return total>2*cal(target)||2*cal(target.left)>total||2*cal(target.right)>total;
    }

    private TreeNode find(int x,TreeNode treeNode) {
        if (treeNode==null){
            return null;
        }
        if (treeNode.val==x){
            return treeNode;
        }
        TreeNode t1=find(x,treeNode.left);
        TreeNode t2=find(x,treeNode.right);
        if (t1!=null){
            return t1;
        }else {
            return t2;
        }
    }

    private int cal(TreeNode root) {
        if (root==null){
            return 0;
        }else {
            if (map.containsKey(root)){
                return map.get(root);
            }else {
                int ans=1+cal(root.left)+cal(root.right);
                map.put(root,ans);
                return ans;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1145().btreeGameWinningMove(new TreeNode(1,new TreeNode(2,new TreeNode(4,new TreeNode(8),new TreeNode(9)),new TreeNode(5,new TreeNode(10),new TreeNode(11))),new TreeNode(3,new TreeNode(6),new TreeNode(7))),11,3));
    }
}
